Not Applicable
Not Applicable
Cyclic Redundancy Check (CRC) is a well-known error detection and correction technique used in many transmission and storage systems. A number of redundant bits are added to a message or data block, so that errors occurring during transmission or storage can be detected and, possibly, corrected. The degree of error detection is a function of the size of the message or data block, and the particular CRC.
One common CRC used in Local Area Networks (LANs) is defined for the ANSI/IEEE Std. 802 family of LAN standards. In that standard, a 4-octet (32-bit) CRC value is loaded into the Frame Check Sequence (FCS) field of a data unit or packet when it is transmitted. The value is computed as a function of the contents of the data unit. The k bits of data covered by the FCS can be represented as a polynomial f(x) of degree kxe2x88x921. For example:
f(x)=10100100=x7+x5+x2 
f(x)=000 . . . 010100100=x7+x5+x2 
f(x)=101001=x5+x3+1
The specific encoding of the CRC value for ANSI/IEEE 802 is defined by the following generating polynomial:
G(x)=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1
In existing ASNI/IEEE systems, the CRC value corresponding to a given data unit is formed by the following procedure:
(1) The first 32 bits of the data unit are complemented.
(2) The k bits of the data unit are then considered to be coefficients of a polynomial f*(x) of degree k=1.
(3) f*(x) is multiplied by x32 and divided by G(x) using modula-2 arithmetic, producing a remainder R(x) of degree less than or equal to 31.
(4) The coefficients of R(x) are considered to be a 32-bit sequence.
(5) The bit sequence is complemented and the result is the CRC value placed in the FCS field.
Steps 1 and 5 allow detection of missing or added zero bits at the beginning of a message. The necessary polynomial division in (3) has a well-known recursive form that processes each bit of the message serially and can be implemented simply in hardware using a linear feedback shift register (LFSR) formed by exclusive-OR gates to perform divisions and registers to hold intermediate results. However, such a serial implementation becomes impractical as data rates increase because only one bit of the message is processed at a time. When the data rate becomes sufficiently high, the serial form cannot generate or check the CRC value of a message within the time it takes to transmit the message. Accordingly, CRC related processing becomes an unacceptable bottleneck on message throughput.
To address this problem, some existing systems have introduced a level of parallelism into CRC processing. These systems have extended the serial implementation to process several bits of the message in parallel, based on a modified recursive equation. The standard parallel CRC method is described in U.S. Pat. No. 4,593,393 of Mead et al., filed Feb. 6, 1984, and U.S. Pat. No. 5,103,451 of Fossey, filed Jan. 29, 1990. However, this standard parallel approach cannot process many bits in parallel because the number of terms in the logic equations it implements becomes excessively large. As a result, many exclusive-OR gates are required, causing the system to run too slow, and which further occupy too much area on a chip and consume too much power. In addition, the standard parallel approach suffers from limited performance due to a low degree of pipelining in its processing.
As the number of bits being processed in parallel increases, the number of message bits covered by the CRC may not always be exactly divisible by the number of bits being processed in parallel. Existing systems for CRC value generation have not addressed this problem, since such existing systems have typically processed 8 bits in parallel, and the messages covered by the CRC value are typically guaranteed to contain an integer number of octets or bytes (8 bit units).
Accordingly it would be desirable to have a system for generating and checking a CRC value that processes many bits in parallel without requiring excessive numbers of exclusive-OR gates. The system should be compatible with existing CRC generation and checking standards, and apply to systems for error detection and correction in communications and storage applications.
Further, a system is needed to provide additional pipelining in the processing of CRC values. In addition, a system is required that enables CRC checking to be performed on messages that are not equally divisible by the number of bits being processed in parallel.
A parallel, recursive system for generating a CRC value for a unit of data is disclosed, in which the feedback and forward terms are separated, and the forward terms are reduced. The unit of data may be either a portion of a data unit that is to be transmitted onto a communications network, a portion of a unit of data that has been received from a communications network, or a data block that has been either read or is to be written to a storage device such as a magnetic disk.
A forward logic block, which implements the forward terms, is responsive to a number of bits received from the unit of data, and operates to perform logic operations based on the reduced forward logic terms on the bits received from the unit of data, in order to produce a first output. In an illustrative embodiment in which the number of bits being processed in parallel, also referred to as the size of the portion of the unit of data, is less than or equal to the size of the CRC value, then the forward logic block is a direct connection to a number of exclusive-OR logic gates.
A feedback logic block, responsive to an output of a remainder register, operates to perform logic operations based on the feedback terms on an output of the remainder register to produce a second output. The second output is also coupled to the exclusive-OR logic gates.
The exclusive-OR logic gates perform a bit-wise exclusive-OR logic operation on the first output and the second output to produce a third output. The third output is coupled to an input of the remainder register.
In an exemplary embodiment, a first pipeline register receives the first output, and the exclusive-OR logic performs the bit-wise exclusive-OR logic operation on the second output and an output of the first pipeline register, instead of on the first output and.the second output. A second pipeline register, having the bits from the data unit as an input, further has an output coupled to a first input of a multiplexer. The multiplexer has a second input coupled to the output of the remainder register. The multiplexer is controlled to select the output of the remainder register in the event that all bits of the data unit have been processed by the first logic block and the second logic block. Otherwise, the multiplexer is controlled to select the bits from the unit of data. This has the effect of appending the CRC or FCS to the message.
In another embodiment, an inverter coupled is coupled to the output of the remainder register, to allow for CRC values with CRC bits inverted.
In another embodiment, the forward logic block determines the first output to be the remainder of the division of a polynomial a(x), by a predetermined generating polynomial G(X), where a(x) corresponds to a subsequence of the unit of data, and wherein a(x) is a polynomial of size jxe2x88x921, where j is equal to a number of bits of the data unit being processed in parallel. The coefficients of a(x) correspond to the bits of the data unit. The feedback logic block determines the second output to be the remainder of the division of a product polynomial by a predetermined generator polynomial G(X), wherein the product polynomial is the result of multiplying the polynomial r(x) by xj, which has the effect of shifting r(x) by j bits in the direction of more significant bits. The coefficients of the polynomial of r(x) correspond to the bits of the remainder register.
In another embodiment, the remainder register is initialized to a predetermined value I(x). I(x) is selected such that the output of said second logic block is all ones (is) in the case where I(x) is an input to said second logic block. I(x) is equal to the hexadecimal value 9226F562 if the generator polynomial is equal to the generator polynomial defined for LANs in IEEE 802. This aspect of the invention is distinct over existing systems in which pre-loading of any result or remainder registers uses an initial value of all is 1s or all 0s.
Thus, a system is disclosed for generating and checking a CRC value that processes many bits in parallel without requiring excessive numbers of exclusive-OR gates. The disclosed system is compatible with existing CRC generation and checking standards, and applies to systems for error detection and correction in communications and storage applications. Further, the disclosed system provides increased pipelining in the processing of CRC values. The disclosed system also enables CRC checking to be performed on messages that are not equally divisible by the number of bits being processed in parallel.